package leetcode_500;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *FindAllDuplicatesInAnArray_442 找出一个数组中重复的元素 元素很特殊  1 ≤ a[i] ≤ n (n = size of array)
 *describe:利用原数组  给元素增加标记位 如果出现了就让其对应下标元素置负数  AC 31%
 *2018年8月20日 上午9:53:17
 */
public class FindAllDuplicatesInAnArray_442 {
	public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res=new ArrayList<Integer>();
        for(int num:nums) {
        	num=Math.abs(num);
        	if(nums[num-1]<0)
        		res.add(num);
        	else
        		nums[num-1]=-nums[num-1];
        }
        return res;
    }
}
